package com.neusoft.sort.quick;

/**
 * @Author lichunlong lcl253137@alibaba-inc.com
 * @Desc 快速排序
 * @Date 2024-11-17
 */
public class QuickSort {

    /**
     * 快速排序: 时间复杂度 O(n^2)
     *
     * @param arr 待排序数组
     */
    public static void quickSort(int[] arr) {
        quickSort(arr, 0, arr.length - 1);
    }

    /**
     * 快速排序: 对指定边界的数组进行快速排序
     *
     * @param arr        待排序数组
     * @param leftIndex  数组左侧值的索引下标
     * @param rightIndex 数组右侧值的索引下标
     */
    public static void quickSort(int[] arr, int leftIndex, int rightIndex) {
        // 选定快速排序的中轴值
        int pivotVal = arr[(leftIndex + rightIndex) / 2];
        // 定义临时变量
        int tempLeftIndex = leftIndex;
        int tempRightIndex = rightIndex;
        while (tempLeftIndex < tempRightIndex) {
            // 在pivot的左侧一直找,直到找到大于等于pivot的值才退出
            while (arr[tempLeftIndex] < pivotVal) {
                tempLeftIndex++;
            }
            // 在pivot的右侧一直找,直到找到小于等于pivot的值才退出
            while (arr[tempRightIndex] > pivotVal) {
                tempRightIndex--;
            }
            // 数组已经完全排序完成
            if (tempLeftIndex >= tempRightIndex) {
                break;
            }
            // 交换中轴值左右两侧的数值
            swap(arr, tempLeftIndex, tempRightIndex);
            // 交换以后后，如果发现这个arr[tempLeftIndex]和pivotVal的值相等, 则tempRightIndex前移
            if (arr[tempLeftIndex] == pivotVal) {
                tempRightIndex--;
            }
            // 交换以后后，如果发现这个arr[tempRightIndex]和pivotVal的值相等, 则tempLeftIndex后移
            if (arr[tempRightIndex] == pivotVal) {
                tempLeftIndex++;
            }
            // 避免无法退出while循环，造成死循环现象
            if (tempLeftIndex == tempRightIndex) {
                tempLeftIndex++;
                tempRightIndex--;
            }
            // 向左递归
            if (leftIndex < tempRightIndex) {
                quickSort(arr, leftIndex, tempRightIndex);
            }
            // 向右递归
            if (rightIndex > tempLeftIndex) {
                quickSort(arr, tempLeftIndex, rightIndex);
            }
        }
    }

    /**
     * 交换指定索引的值
     *
     * @param arr        待排序数组
     * @param leftIndex  中轴左侧比中轴大的数的下标
     * @param rightIndex 中轴右侧比中轴小的数的下标
     */
    public static void swap(int[] arr, int leftIndex, int rightIndex) {
        int temp = arr[leftIndex];
        arr[leftIndex] = arr[rightIndex];
        arr[rightIndex] = temp;
    }
}
